#define _CRT_SECURE_NO_WARNINGS 1
//TOPK问题
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
void print(int* a, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void AdJustDown(int* a,int size,int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		
		if (child+1<size && a[child] > a[child + 1])
		{
			++child;
		}
		if (a[parent] > a[child])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//getLeastNumbers1
int * getLeastNumbers1(int* a, int size,int k)
{
	//建堆
	for (int i = (size-1-1)/2; i >= 0 ; i--)
	{
		AdJustDown(a, size, i);
	}
	//排序
	int end = size - 1;
	while (end  > 0)
	{
		Swap(&a[0], &a[end]);
		AdJustDown(a, end, 0);
		end--;
	}
	print(a, size);
	//将最大的前五个存到新数组中
	int* toparr =(int *)malloc(sizeof(int) * k);
	if (toparr == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	for (int  i = 0; i < k; i++)
	{
		toparr[i] = a[i];
	}
	return toparr;
}

void Creatdata()
{
	int n = 10000000;
	srand(time(NULL));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (int  i = 0; i < n; i++)
	{
		int x = (rand() + i) % 10000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}
getLeastNumbers2(const char* filename, int k)
{
	
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror(fopen);
		exit(-1);
	}
	int* toparr = (int*)malloc(sizeof(int) * k);
	if (toparr == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	//从文件中读k个数存放到数组中
	for (int  i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &toparr[i]);
	}
	//建堆 用a中前k个建堆
	for (int  i = (k-1-1)/2; i >= 0; i--)
	{
		AdJustDown(toparr, k, i);
	}

	//将剩余n-k个元素与堆顶元素交换 让最大的进堆
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > toparr[0])
		{
			toparr[0] = x;
			AdJustDown(toparr, k, 0);
		}
	}


	for (int i = 0; i < k; i++)
	{
		printf("%d ", toparr[i]);
	}
	printf("\n");

	free(toparr);
	fclose(fout);


}
int main()
{
	int a[] = { 93,1,2,5,61,9,1,236,15,222,999 };
	int sz = sizeof(a) / sizeof(int);
	int k = 5;
	/*int *topa = getLeastNumbers1(a, sz,k);
	for (int  i = 0; i < k; i++)
	{
		printf("%d ", topa[i]);
	}
	free(topa);
	topa = NULL;*/

	//在文件中解决topk问题
	//创建1000万个数据的文件
	//Creatdata();
	getLeastNumbers2("data.txt", k);

	return 0;
}